package com.leetcode.algorithm.y19.m03;

/**
 * leetcode-cn.com
 * @author: jie.deng
 * @time: 2019年3月29日 上午11:37:41
 */
public class MySolution0329 {
	
	/**
	 * 754. 到达终点数字
	 * 
	 * 在一根无限长的数轴上，你站在0的位置。终点在target的位置。
	 * 
	 * 每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。
	 * 
	 * 返回到达终点需要的最小移动次数。
	 * 
	 * 示例 1:
	 * 
	 * 输入: target = 3 输出: 2 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 3 。 示例 2:
	 * 
	 * 输入: target = 2 输出: 3 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 -1 。 第三次移动，从 -1 到 2
	 * 。 注意:
	 * 
	 * target是在[-10^9, 10^9]范围中的非零整数。
	 * 
	 * @param target
	 * @return
	 */
	public int reachNumber(int target) {
		// 从1到N一直累加, 直到SUM==TARGET, 或SUM减TARGET为正偶数. 因为在第n步往回走一次,SUM就会减少2n,所以他们的差必须是偶数才能到.
		target = Math.abs(target);
		int sum = 0;
		int nextStep = 1;
		while (sum < target || (sum - target) % 2 == 1) {
			sum += nextStep;
			nextStep++;
		}
		return nextStep - 1;
	}
    
}
